﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Demo.Framework.Algorithm.Sort
{
    /* Set i=0
     * Scan from i to 0
     * If a[i] < a[i-1] then swap | i-1>=0
     * Increment i
     * Repeat process
     * Advantages
     * 
     * Disadvantages
     * Not efficient for large data set
     * Complexity - N^2
     * */
    class InsertionSort<T> where T:IComparable
    {
        public void Sort(T[] list)
        {
            int count = list.Length;
            for (int i = 0; i < count; i++)
            {
                for (int j = i; j >0; j--)
                {
                    if (IsLess(list[j], list[j-1]))
                    {
                        Swap(list, j, j-1);
                    }
                }
            }
        }

        private bool IsLess(T x, T y)
        {
            return x.CompareTo(y) == -1 ? true : false;
        }

        private void Swap(T[] array, int x, int y)
        {
            T temp = array[x];
            array[x] = array[y];
            array[y] = temp;
        }
    }
}
